/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: hp
 * Date: 2024-03-28
 * Time: 14:56
 */


public class Test {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode pcur = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                while(pcur != slow) {
                    slow = slow.next;
                    pcur = pcur.next;
                }
                return pcur;
            }
        }
        return null;
    }



    /*public boolean hasCycle(ListNode head) {
        if(head == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;

        while(slow != fast) {
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }*/



    /*public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA;
        ListNode pb = headB;
        int lenA = 0;
        int lenB = 0;
        while(pa != null) {
            pa = pa.next;
            lenA++;
        }
        while(pb != null) {
            pb = pb.next;
            lenB++;
        }
        pa = headA;
        pb = headB;
        int len = lenA - lenB;
        if(len < 0) {
            ListNode tmp = pa;
            pa = pb;
            pb = tmp;
            len = lenB - lenA;
        }
        while(len > 0) {
            pa = pa.next;
            len--;
        }
        while(pa != pb) {
            pa = pa.next;
            pb = pb.next;
        }
        if(pa == null) {
            return null;
        }
        return pa;
    }*/


    /*public boolean chkPalindrome(ListNode A) {
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode pcur = slow.next;
        while(pcur != null) {
            ListNode pnext = pcur.next;
            pcur.next = slow;
            slow = pcur;
            pcur = pnext;
        }
        ListNode cur = A;
        while(slow != cur && slow.next != cur) {
            if(slow.val != cur.val) {
                return false;
            }
            slow = slow.next;
            cur = cur.next;
        }
        return true;
    }
*/

    /*public ListNode partition(ListNode pHead, int x) {
        if(pHead == null) {
            return null;
        }

        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;

        ListNode pcur = pHead;
        while(pcur != null) {
            if(pcur.val < x) {
                if(as == null) {
                    as = pcur;
                    ae = pcur;
                }else {
                    ae.next = pcur;
                    ae = ae.next;
                }
            }else {
                if(bs == null) {
                    bs = pcur;
                    be = pcur;
                }else {
                    be.next = pcur;
                    be = be.next;
                }
            }
            pcur = pcur.next;
        }
        if(be != null) {
            be.next = null;
        }

        if(as == null) {
            return bs;
        }


        ae.next = bs;

        return as;
    }*/


    /*public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }

        if(list2 == null) {
            return list1;
        }

        ListNode headA = list1;
        ListNode headB = list2;
        ListNode newhead = null;
        ListNode pcur = null;

        while(headA != null && headB != null) {
            if(headA.val < headB.val) {
                if(newhead == null) {
                    newhead = headA;
                    pcur = newhead;
                }else {
                    pcur.next = headA;
                    pcur = pcur.next;
                }
                headA = headA.next;
            }else {
                if(newhead == null) {
                    newhead = headB;
                    pcur = newhead;
                }else {
                    pcur.next = headB;
                    pcur = pcur.next;
                }
                headB = headB.next;
            }
        }
        if(headA == null) {
            pcur.next = headB;
        }
        if(headB == null) {
            pcur.next = headA;
        }
        return newhead;
    }*/

    /*public int kthToLast(ListNode head, int k) {
        if(k < 0) {
            return -1;
        }
        ListNode pcur = head;
        ListNode prev = head;
        while(k!=0) {
            pcur = pcur.next;
            if(pcur == null) {
                return -1;
            }
            k--;
        }
        while(pcur != null) {
            pcur = pcur.next;
            prev = prev.next;
        }
        return prev.val;
    }*/


    /*public ListNode middleNode(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }*/



   /* public ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }

        ListNode pcur = head;
        ListNode prev = null;
        while(pcur != null) {
            ListNode pnext = pcur.next;
            pcur.next = prev;
            prev = pcur;
            pcur = pnext;
        }
        return prev;
    }*/



   /* public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return head;
        }
        ListNode pcur = head.next;
        ListNode prev = head;

        while(pcur != null) {
            if(pcur.val == val) {
                prev.next = pcur.next;
                pcur = pcur.next;
            }else {
                prev = pcur;
                pcur = pcur.next;
            }
        }
        if(head.val == val) {
            head = head.next;
        }
        return head;
    }*/
}
